1. Field of the Invention
The present disclosure relates generally to packet networks, and more particularly to the operation of traffic-engineered label-switched paths within such networks.
2. Description of Related Art
In a packet network, “nodes” or “routers” share network address information that allows each node or router to forward packets toward their respective destination networks. For networks defined using the Internet Protocol, each node is provisioned with a network address that identifies the particular network the system is on, and with a system or host address that uniquely identifies the node. These addresses are shared among neighboring nodes to allow each router to build a “tree” with itself as the root node and next-hop paths from itself to every address on the network.
Routers use IP network and host addresses to forward routed traffic internally on a packet network according to an internal routing (or gateway) protocol (an “IGP”). Some common internal gateway protocols in use today include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS). OSPF is further described in Internet Engineering Task Force (IETF) Request for Comments (RFC) 2328, “OSPF Version 2,” by J. Moy, April 1998, and IETF RFC 2740, “OSPF for IPv6,” R. Coltun, December 1999. IS-IS is further described in the International Organization for Standardization (ISO) document ISO 8473, “Intermediate System to Intermediate System Routing Information Exchange Protocol for Providing the Connectionless-mode Network Service,” ISO/IEC 10589:2002, 2nd Ed.
OSPF and IS-IS are examples of link-state protocols. A “link” can be considered to be an interface or port on a router, or an aggregation of such interfaces or ports that are treated as a single link by the routing protocol (FIG. 1A shows a logical link LL5 that is an aggregation of three physical links). The state of each link contains a description of the interface and what routers/networks are reachable through that link. In OSPF, a link-state database would contain the IP address of the interface/device, the subnet mask and other information describing the network, a list of routers connected to that network, a cost of sending packets across that interface, etc.
OSPF routers use link-state advertisements (LSAs) to share information from their link-state databases with neighboring routers in the same autonomous system. Whenever an interface is brought up or a change in routing information known to the router occurs, the router generates a LSA to inform its neighbors of the new or changed link-state information. When a neighbor router receives the LSA, it updates its own link-state database and then propagates the information in another LSA to its neighbors. Thus the LSA is flooded to all routers, and all routers contain the same link-state database.
Whenever a router receives an update to its link-state database, it uses a shortest path algorithm (the Dijkstra algorithm) to calculate a shortest path tree to all destinations, based on the accumulated costs associated with the links used to reach each destination. The shortest path tree will differ for each router, as each places itself at the root of the tree, but all routers should agree with each other as to routes. In other words, no routing loops should exist where node A thinks that a destination should be reached through a node B, and node B thinks that the destination should be reached through node A.
In order to place limits on the flooding of LSAs, OSPF allows routers in the same autonomous system to be grouped into areas. For instance, FIG. 1A depicts two areas A0, A1 of an autonomous system (AS) 100. Every AS must have an area 0 or backbone area. Generally, all other areas connect to the backbone area, although provisions exist for transit areas.
Routers are classified according to their position in the AS. An internal router has all of its interfaces in the same area. In area A1, routers LSR1 and LSR2 are internal routers. An area border router (ABR) has interfaces in multiple areas of the AS. LER1 has two interfaces (L2 and L3) in area A1, and at least one interface in another area (L0 in area A0), and is thus an ABR. An autonomous system boundary router (ASBR) has at least one interface in an area of the AS and at least one interface to another AS or running another routing protocol. The ASBR selectively redistributes information received from the foreign network/protocol within OSPF. In FIG. 1A, routers LER1 and LER2 are ASBRs. Both LER1 and LER2 communicate, over link L1 and links L9 and L10, respectively, with routers (not shown) outside of the AS using an external gateway protocol, such as Border Gateway Protocol (BGP).
Although OSPF and IS-IS provide one method to direct traffic across a packet network, other methods exist. For instance, protocols such as Multi-Protocol Label Switching (MPLS) allow packets to be routed across a packet network using small “labels” or “tags” inserted in the packets. Neighboring routers agree beforehand that packets transmitted from an upstream router to a downstream router with a given label will be forwarded along a unidirectional “label-switched path” (LSP) that has been pre-arranged. A LSP is essentially a tunnel set up between two “label edge routers” (LERs), one of which receives the packets and inserts the first label, and the other of which removes the last label and forwards the packet using other means (such as a traditional routing protocol). Other routers along the path are termed “label-switching routers” (LSRs), due to their function of switching incoming labels they recognize for outgoing labels that their downstream neighbor will recognize. Generally, the packets traversing a LSP belong to a common “Forwarding Equivalent Class” (FEC) that can be routed efficiently using the two LERs as points along the routing path.
One use for MPLS LSPs is in the operation of a traffic-engineered network. Using shortest-path routing algorithms, it is difficult to guide specific traffic towards underutilized paths, and thus the “shortest” paths tend to be overutilized, decreasing network performance as a whole. In a traffic-engineered (TE) network, different constraints such as link utilization and which links can guarantee a given bandwidth, latency, etc., enter in to the selection of a path, e.g., using a “constraint-based routing” algorithm. Once an appropriate path is found for a traffic stream, an MPLS traffic-engineered LSP tunnel can be set up to forward that traffic stream.
In order to use constraint-based routing to reach a remote endpoint, an ingress endpoint must know more than just the traditional IGP link state information. As shown in FIG. 1B, the nodes in a TE network flood TE LSAs throughout the network. For instance, LSR1 sends TE LSAs to LER1, LSR2, and LSR3, reporting traffic engineering information on outgoing links L2, L4, and LL5. LSR1 also floods TE LSAs that it receives from LER1, LSR2, and LSR3 to the others in this group. LER1, upon receiving TE LSAs, builds a Traffic Engineering Database (TED) for area A1, from which it can construct MPLS LSPs.
FIG. 2 shows the general format of an OSPF TE LSA 200. TE LSA 200 contains a standard OSPF LSA header, marked as an Opaque TE LSA. Each TE LSA contains two TLVs (Type-Length-Value fields)—a router address TLV (which identifies the router that generated the LSA) and a link TLV. The link TLV contains between two and nine sub-TLVs, of the types shown in FIG. 2. These TLVs describe the link, its traffic engineering attributes, and its bandwidth attributes.
An edge router can examine its link-state database and traffic engineering database and determine a path across a network area that it believes to be a good fit for a traffic class. The edge router can attempt to set up this path by issuing an MPLS-TE path message, using protocol packets such as Resource ReSerVation Protocol (RSVP) packets, including an Explicit Route Object that specifies the path to be taken. FIG. 1C shows an example. LER1 determines that a given traffic class should be traffic engineered on an explicit route LSR1-LSR2-LER2. LER1 generates an RSVP path message to LSR1. Assuming LSR1 can meet the bandwidth request on LL5, LSR1 propagates the RSVP path message to LSR2. When LSR2 can also meet the bandwidth request on L7, LSR2 propagates the RSVP path message to LER2.
When the receiving LER receives an RSVP path message, it generates an RSVP return reservation request and sends it back to the LSR from which it received the RSVP path message. FIG. 1D shows an example. LER2 generates an RSVP return reservation request (RREQ) that identifies the RSVP path message of FIG. 1C, and specifies a label to be applied to packets sent over this LSP to LER2. LER2 sends RREQ to LSR2, which reserves the requested bandwidth on L7. LSR2 generates an RSVP RREQ packet with a label to be applied to packets sent over this LSP to LSR2, and sends RREQ to LSR1. LSR2 creates an entry in its forwarding database, identifying the labels to be swapped for the LSP, and an outgoing interface (link L7) to be used. LSR1 performs similar functions as LSR2.
When LER1 receives RREQ from LSR1, it may now use its LSP by modifying packets of the given FEC with an MPLS header containing the label supplied by LSR1 and forwarding them on L2. FIG. 1E shows an example of the MPLS LSP segments, where LSR1 has instructed LER1 to use an MPLS label T1, LSR2 has instructed LSR1 to use an MPLS label T2, and LER2 has instructed LSR2 to use an MPLS label T3. As shown in FIG. 1F, LER1 receives packets of the requested forwarding equivalence class FEC1, e.g., on link L1. The packets are modified with an MPLS header to traverse the links L2, LL5, and L7, respectively, with labels T1, T2, and T3 inserted respectively by LER1, LSR1, and LSR2. LER2 removes the MPLS header and forwards the packets FEC1 out an appropriate interface, e.g., L9, using an appropriate IP routing protocol.
MPLS, RSVP, and Traffic Engineering are complex inter-related subjects with voluminous design documents that describe operation in further detail. The following Internet Engineering Task Force (IETF) documents describe various features useful in understanding the framework underlying the embodiments in additional detail, and are incorporated herein by reference: IETF Request For Comments (RFC) 2205, S. Berson et al., “Resource ReSerVation Protocol (RSVP),” September 1997; IETF RFC 2702, D. Awduche et al., “Requirements for Traffic Engineering Over MPLS,” September 1999; IETF RFC 3031, E. Rosen et al., “Multiprotocol Label Switching Architecture,” January 2001; IETF RFC 3209, D. Awduche et al., “RSVP-TE: Extensions to RSVP for LSP Tunnels,” December 2001; IETF RFC 3477, K. Kompella et al., “Signalling Unnumbered Links in Resource ReSerVation Protocol-Traffic Engineering (RSVP-TE), January 2003; IETF RFC 3630, D. Katz et al., “Traffic Engineering (TE) Extensions to OSPF Version 2,” September 2003; IETF RFC 3945, E. Mannie, “Generalized Multi-Protocol Label Switching (GMPLS) Architecture,” October 2004; IETF RFC 4090, P. Pan et al., “Fast Reroute Extensions to RSVP-TE for LSP Tunnels,” May 2005; IETF RFC 4203, K. Kompella et al., “OSPF Extensions in Support of Generalized Multi-Protocol Label Switching (GMPLS),” October 2005; IETF RFC 4220, M. Dubuc et al., “Traffic Engineering Link Management Information Base,” November 2005. Other RFCs exist, including those for creating label-switched traffic-engineered paths with IS-IS and MPLS competitor protocols, such as Constraint-Routing Label Distribution Protocol (CR-LDP). The list above provides a representative tabulation of MPLS-TE concepts understood by those skilled in the art.